package strings;

/**
 * 28. 实现 strStr()
 * <p>
 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
 * <p>
 * 说明：
 * <p>
 * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * <p>
 * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
 */
public class N28_StrStr {
    // 使用API直接得到，太捞了
    public int strStr_API(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    // KMP算法
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1))
                j = next[j];
            if (haystack.charAt(i) == needle.charAt(j + 1))
                j++;
            if (j == needle.length() - 1)
                return (i - needle.length() + 1);
        }
        return -1;
    }

    /**
     * 构造next数组
     */
    private void getNext(int[] next, String s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1))
                j = next[j];
            if (s.charAt(i) == s.charAt(j + 1))
                j++;
            next[i] = j;
        }
    }

    public static void main(String[] args) {
        N28_StrStr solution = new N28_StrStr();
        System.out.println(solution.strStr("aabaabaaf", "aabaaf"));
    }
}
